/*
 *  功能说明：提供四种常用链表/队列数据结构的宏定义实现，包括：
 *           1. 单链表（SLIST）：单向链接，仅支持头操作，结构简单
 *           2. 单链尾队列（STAILQ）：单向链接+尾指针，支持高效尾插
 *           3. 双向链表（LIST）：双向链接，支持任意位置插入/删除
 *           4. 双向尾队列（TAILQ）：双向链接+尾指针，兼顾灵活性与效率
 *           这些结构用于高效管理有序或无序数据集合，协程库中常用TAILQ管理就绪协程（FIFO调度），
 *           LIST管理需要双向遍历的场景（如忙碌协程列表）。
 */

#ifndef __NTY_QUEUE_H__
#define __NTY_QUEUE_H__

#include <sys/cdefs.h>

/* 调试相关宏（默认关闭，开启后记录节点/头结构的修改轨迹） */
#ifdef QUEUE_MACRO_DEBUG
/* 存储节点/头结构的最后两次修改位置（文件路径+行号） */
struct qm_trace {
	char *lastfile;   // 最后一次修改的文件
	int lastline;     // 最后一次修改的行号
	char *prevfile;   // 上一次修改的文件
	int prevline;     // 上一次修改的行号
};

#define	TRACEBUF	struct qm_trace trace;  // 为头/节点结构添加调试轨迹字段
#define	TRASHIT(x)	do {(x) = (void *)-1;} while (0)  // 标记已删除的指针（避免野指针）

/* 更新头结构的调试轨迹（记录当前文件和行号） */
#define	QMD_TRACE_HEAD(head) do {							\
	(head)->trace.prevline = (head)->trace.lastline;		\
	(head)->trace.prevfile = (head)->trace.lastfile;		\
	(head)->trace.lastline = __LINE__;						\
	(head)->trace.lastfile = __FILE__;						\
} while (0)

/* 更新节点结构的调试轨迹（记录当前文件和行号） */
#define	QMD_TRACE_ELEM(elem) do {							\
	(elem)->trace.prevline = (elem)->trace.lastline;		\
	(elem)->trace.prevfile = (elem)->trace.lastfile;		\
	(elem)->trace.lastline = __LINE__;						\
	(elem)->trace.lastfile = __FILE__;						\
} while (0)

#else
/* 关闭调试时，调试宏为空操作 */
#define	QMD_TRACE_ELEM(elem)
#define	QMD_TRACE_HEAD(head)
#define	TRACEBUF
#define	TRASHIT(x)
#endif	/* QUEUE_MACRO_DEBUG */


// ==========================================
// 第一部分：单链表（SLIST）
// 特性：单向链接，仅包含"下一个节点"指针，不支持反向遍历。
// 优势：结构最简单，内存开销小，头插/头删效率为O(1)。
// 劣势：尾插/中间删除需遍历，效率为O(n)。
// 适用场景：仅需在头部操作、无需反向遍历的简单场景（如临时缓存列表）。
// ==========================================

/*
 * 定义单链表的头结构
 * 参数：
 *   name：链表名称（用于区分不同链表）
 *   type：链表节点的数据类型
 * 结构说明：
 *   slh_first：指向链表的第一个节点（链表的唯一入口）
 */
#define	SLIST_HEAD(name, type)								\
struct name {												\
	struct type *slh_first;	/* 指向第一个节点 */			\
}

/*
 * 静态初始化单链表头（定义时直接初始化）
 * 示例：SLIST_HEAD(mylist, node) list = SLIST_HEAD_INITIALIZER(list);
 */
#define	SLIST_HEAD_INITIALIZER(head)						\
	{ NULL }  /* 初始化为空链表（头指针为NULL） */

/*
 * 定义单链表的节点结构（每个节点需包含此字段作为链接）
 * 参数：type：节点的数据类型
 * 结构说明：
 *   sle_next：指向当前节点的下一个节点（单向链接）
 */
#define	SLIST_ENTRY(type)									\
struct {													\
	struct type *sle_next;	/* 指向 next 节点 */			\
}

/* 单链表核心操作宏 */

/* 判断单链表是否为空（头指针为NULL则为空） */
#define	SLIST_EMPTY(head)	((head)->slh_first == NULL)

/* 获取单链表的第一个节点 */
#define	SLIST_FIRST(head)	((head)->slh_first)

/*
 * 正向遍历单链表（遍历过程中不可删除节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：链表头
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_FOREACH(var, head, field)						\
	for ((var) = SLIST_FIRST((head));						\
	    (var);												\
	    (var) = SLIST_NEXT((var), field))

/*
 * 安全正向遍历单链表（遍历过程中可删除当前节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：链表头
 *   field：节点中SLIST_ENTRY字段的名称
 *   tvar：临时变量（保存下一个节点，避免删除当前节点后丢失指针）
 */
#define	SLIST_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = SLIST_FIRST((head));						\
	    (var) && ((tvar) = SLIST_NEXT((var), field), 1);	\
	    (var) = (tvar))

/*
 * 通过指针地址遍历单链表（支持在遍历中插入/删除节点）
 * 参数：
 *   var：当前节点指针
 *   varp：当前节点的指针的地址（用于修改指针指向）
 *   head：链表头
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_FOREACH_PREVPTR(var, varp, head, field)		\
	for ((varp) = &SLIST_FIRST((head));						\
	    ((var) = *(varp)) != NULL;							\
	    (varp) = &SLIST_NEXT((var), field))

/* 动态初始化单链表（将头指针设为NULL，清空链表） */
#define	SLIST_INIT(head) do {								\
	SLIST_FIRST((head)) = NULL;								\
} while (0)

/*
 * 在指定节点后插入新节点
 * 参数：
 *   slistelm：基准节点（新节点插入到它后面）
 *   elm：待插入的新节点
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_INSERT_AFTER(slistelm, elm, field) do {			\
	SLIST_NEXT((elm), field) = SLIST_NEXT((slistelm), field);	\
	SLIST_NEXT((slistelm), field) = (elm);						\
} while (0)

/*
 * 在链表头部插入新节点（头插法，O(1)）
 * 参数：
 *   head：链表头
 *   elm：待插入的新节点
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_INSERT_HEAD(head, elm, field) do {				\
	SLIST_NEXT((elm), field) = SLIST_FIRST((head));				\
	SLIST_FIRST((head)) = (elm);								\
} while (0)

/* 获取节点的下一个节点 */
#define	SLIST_NEXT(elm, field)	((elm)->field.sle_next)

/*
 * 从链表中删除指定节点（需遍历找到前驱节点，O(n)）
 * 参数：
 *   head：链表头
 *   elm：待删除的节点
 *   type：节点的数据类型
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_REMOVE(head, elm, type, field) do {			\
	if (SLIST_FIRST((head)) == (elm)) {					\
		SLIST_REMOVE_HEAD((head), field);					\
	} else {												\
		struct type *curelm = SLIST_FIRST((head));			\
		/* 遍历找到待删除节点的前驱 */						\
		while (SLIST_NEXT(curelm, field) != (elm))			\
			curelm = SLIST_NEXT(curelm, field);				\
		SLIST_REMOVE_AFTER(curelm, field);					\
	}														\
	TRASHIT((elm)->field.sle_next);	/* 标记已删除 */		\
} while (0)

/*
 * 删除指定节点的下一个节点（O(1)）
 * 参数：
 *   elm：基准节点（删除它的下一个节点）
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define SLIST_REMOVE_AFTER(elm, field) do {					\
	SLIST_NEXT(elm, field) = SLIST_NEXT(SLIST_NEXT(elm, field), field);	\
} while (0)

/*
 * 删除链表的头部节点（头删法，O(1)）
 * 参数：
 *   head：链表头
 *   field：节点中SLIST_ENTRY字段的名称
 */
#define	SLIST_REMOVE_HEAD(head, field) do {					\
	SLIST_FIRST((head)) = SLIST_NEXT(SLIST_FIRST((head)), field);	\
} while (0)


// ==========================================
// 第二部分：单链尾队列（STAILQ）
// 特性：单向链接+尾指针，在单链表基础上增加尾指针，支持高效尾插。
// 优势：尾插效率为O(1)，保留单链表的简单性，适合实现FIFO队列。
// 劣势：仍不支持反向遍历，中间删除需遍历（O(n)）。
// 适用场景：需要频繁在尾部插入的FIFO场景（如任务队列）。
// ==========================================

/*
 * 定义单链尾队列的头结构
 * 参数：
 *   name：队列名称
 *   type：节点的数据类型
 * 结构说明：
 *   stqh_first：指向队列的第一个节点
 *   stqh_last：指向队列最后一个节点的"next指针的地址"（用于高效尾插）
 */
#define	STAILQ_HEAD(name, type)									\
struct name {													\
	struct type *stqh_first;	/* 指向第一个节点 */			\
	struct type **stqh_last;	/* 指向最后一个节点的next指针地址 */	\
}

/*
 * 静态初始化单链尾队列头
 * 示例：STAILQ_HEAD(myqueue, node) queue = STAILQ_HEAD_INITIALIZER(queue);
 */
#define	STAILQ_HEAD_INITIALIZER(head)							\
	{ NULL, &(head).stqh_first }  /* 初始时尾指针指向头的first字段 */

/*
 * 定义单链尾队列的节点结构（与单链表节点相同，仅单向链接）
 * 参数：type：节点的数据类型
 */
#define	STAILQ_ENTRY(type)										\
struct {														\
	struct type *stqe_next;	/* 指向 next 节点 */				\
}

/* 单链尾队列核心操作宏 */

/*
 * 合并两个单链尾队列（将head2合并到head1尾部，head2清空）
 * 参数：
 *   head1：目标队列（合并后保存所有节点）
 *   head2：源队列（合并后为空）
 */
#define	STAILQ_CONCAT(head1, head2) do {				\
	if (!STAILQ_EMPTY((head2))) {						\
		*(head1)->stqh_last = (head2)->stqh_first;		/* 链接两个队列 */	\
		(head1)->stqh_last = (head2)->stqh_last;		/* 更新head1的尾指针 */	\
		STAILQ_INIT((head2));							/* 清空head2 */		\
	}													\
} while (0)

/* 判断单链尾队列是否为空 */
#define	STAILQ_EMPTY(head)	((head)->stqh_first == NULL)

/* 获取单链尾队列的第一个节点 */
#define	STAILQ_FIRST(head)	((head)->stqh_first)

/*
 * 正向遍历单链尾队列（遍历过程中不可删除节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_FOREACH(var, head, field)				\
	for((var) = STAILQ_FIRST((head));					\
	   (var);											\
	   (var) = STAILQ_NEXT((var), field))

/*
 * 安全正向遍历单链尾队列（遍历过程中可删除当前节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   field：节点中STAILQ_ENTRY字段的名称
 *   tvar：临时变量（保存下一个节点）
 */
#define	STAILQ_FOREACH_SAFE(var, head, field, tvar)				\
	for ((var) = STAILQ_FIRST((head));						\
	    (var) && ((tvar) = STAILQ_NEXT((var), field), 1);		\
	    (var) = (tvar))

/* 动态初始化单链尾队列（清空队列） */
#define	STAILQ_INIT(head) do {							\
	STAILQ_FIRST((head)) = NULL;						\
	(head)->stqh_last = &STAILQ_FIRST((head));			/* 尾指针指向头的first字段 */	\
} while (0)

/*
 * 在指定节点后插入新节点
 * 参数：
 *   head：队列头（可能需要更新尾指针）
 *   tqelm：基准节点（新节点插入到它后面）
 *   elm：待插入的新节点
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_INSERT_AFTER(head, tqelm, elm, field) do {		\
	if ((STAILQ_NEXT((elm), field) = STAILQ_NEXT((tqelm), field)) == NULL)\
		(head)->stqh_last = &STAILQ_NEXT((elm), field);		/* 若插入到尾部，更新尾指针 */	\
	STAILQ_NEXT((tqelm), field) = (elm);				\
} while (0)

/*
 * 在队列头部插入新节点（头插法，O(1)）
 * 参数：
 *   head：队列头
 *   elm：待插入的新节点
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_INSERT_HEAD(head, elm, field) do {			\
	if ((STAILQ_NEXT((elm), field) = STAILQ_FIRST((head))) == NULL)	\
		(head)->stqh_last = &STAILQ_NEXT((elm), field);		/* 若队列为空，尾指针指向新节点的next */	\
	STAILQ_FIRST((head)) = (elm);					\
} while (0)

/*
 * 在队列尾部插入新节点（尾插法，O(1)，核心优势）
 * 参数：
 *   head：队列头
 *   elm：待插入的新节点
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_INSERT_TAIL(head, elm, field) do {			\
	STAILQ_NEXT((elm), field) = NULL;				/* 新节点为最后一个，next为NULL */	\
	*(head)->stqh_last = (elm);					/* 尾指针指向的地址（上一个节点的next）赋值为新节点 */	\
	(head)->stqh_last = &STAILQ_NEXT((elm), field);			/* 更新尾指针为新节点的next地址 */	\
} while (0)

/*
 * 获取单链尾队列的最后一个节点（通过尾指针计算，O(1)）
 * 参数：
 *   head：队列头
 *   type：节点的数据类型
 *   field：节点中STAILQ_ENTRY字段的名称
 * 原理：尾指针stqh_last是最后一个节点的next指针的地址，通过偏移计算节点地址。
 */
#define	STAILQ_LAST(head, type, field)					\
	(STAILQ_EMPTY((head)) ?						\
		NULL :							\
	        ((struct type *)(void *)				\
		((char *)((head)->stqh_last) - __offsetof(struct type, field))))

/* 获取节点的下一个节点 */
#define	STAILQ_NEXT(elm, field)	((elm)->field.stqe_next)

/*
 * 从队列中删除指定节点（需遍历找到前驱节点，O(n)）
 * 参数：
 *   head：队列头
 *   elm：待删除的节点
 *   type：节点的数据类型
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_REMOVE(head, elm, type, field) do {			\
	if (STAILQ_FIRST((head)) == (elm)) {					\
		STAILQ_REMOVE_HEAD((head), field);					\
	} else {													\
		struct type *curelm = STAILQ_FIRST((head));			\
		/* 遍历找到待删除节点的前驱 */							\
		while (STAILQ_NEXT(curelm, field) != (elm))			\
			curelm = STAILQ_NEXT(curelm, field);				\
		STAILQ_REMOVE_AFTER(head, curelm, field);				\
	}															\
	TRASHIT((elm)->field.stqe_next);	/* 标记已删除 */			\
} while (0)

/*
 * 删除队列的头部节点（头删法，O(1)）
 * 参数：
 *   head：队列头
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define	STAILQ_REMOVE_HEAD(head, field) do {					\
	if ((STAILQ_FIRST((head)) = STAILQ_NEXT(STAILQ_FIRST((head)), field)) == NULL)	\
		(head)->stqh_last = &STAILQ_FIRST((head));	/* 若删除后为空，尾指针重置 */	\
} while (0)

/*
 * 删除指定节点的下一个节点（O(1)）
 * 参数：
 *   head：队列头（可能需要更新尾指针）
 *   elm：基准节点（删除它的下一个节点）
 *   field：节点中STAILQ_ENTRY字段的名称
 */
#define STAILQ_REMOVE_AFTER(head, elm, field) do {				\
	if ((STAILQ_NEXT(elm, field) = STAILQ_NEXT(STAILQ_NEXT(elm, field), field)) == NULL)	\
		(head)->stqh_last = &STAILQ_NEXT((elm), field);	/* 若删除的是尾节点，更新尾指针 */	\
} while (0)

/*
 * 交换两个单链尾队列的内容（O(1)）
 * 参数：
 *   head1、head2：两个队列头
 *   type：节点的数据类型
 */
#define STAILQ_SWAP(head1, head2, type) do {				\
	struct type *swap_first = STAILQ_FIRST(head1);			\
	struct type **swap_last = (head1)->stqh_last;			\
	STAILQ_FIRST(head1) = STAILQ_FIRST(head2);				\
	(head1)->stqh_last = (head2)->stqh_last;				\
	STAILQ_FIRST(head2) = swap_first;						\
	(head2)->stqh_last = swap_last;							\
	/* 若交换后队列为空，重置尾指针 */							\
	if (STAILQ_EMPTY(head1))								\
		(head1)->stqh_last = &STAILQ_FIRST(head1);			\
	if (STAILQ_EMPTY(head2))								\
		(head2)->stqh_last = &STAILQ_FIRST(head2);			\
} while (0)


// ==========================================
// 第三部分：双向链表（LIST）
// 特性：双向链接，每个节点包含"前向指针地址"和"后向指针"，支持双向遍历。
// 优势：可在任意位置插入/删除（O(1)），支持正向/反向遍历。
// 劣势：无尾指针，尾操作需遍历（O(n)），结构较复杂。
// 适用场景：需要频繁在中间插入/删除、双向遍历的场景（如双向缓存列表）。
// ==========================================

/*
 * 定义双向链表的头结构
 * 参数：
 *   name：链表名称
 *   type：节点的数据类型
 * 结构说明：
 *   lh_first：指向链表的第一个节点（链表入口）
 */
#define	LIST_HEAD(name, type)							\
	struct name {										\
		struct type *lh_first;	/* 指向第一个节点 */ 	\
	}

/*
 * 静态初始化双向链表头
 * 示例：LIST_HEAD(mylist, node) list = LIST_HEAD_INITIALIZER(list);
 */
#define	LIST_HEAD_INITIALIZER(head)						\
		{ NULL }  /* 初始化为空链表 */

/*
 * 定义双向链表的节点结构（每个节点需包含此字段作为链接）
 * 参数：type：节点的数据类型
 * 结构说明：
 *   le_next：指向当前节点的下一个节点（后向指针）
 *   le_prev：指向当前节点的前一个节点的"le_next指针的地址"（前向指针地址，用于反向遍历和修改）
 */
#define	LIST_ENTRY(type)								\
struct {											\
	struct type *le_next;	/* 指向 next 节点 */	\
	struct type **le_prev;	/* 指向 prev 节点的le_next指针地址 */	\
}

/* 双向链表核心操作宏（含调试检查，默认关闭） */
#if (defined(_KERNEL) && defined(INVARIANTS))
/* 调试时检查头节点的第一个节点的前驱是否正确 */
#define	QMD_LIST_CHECK_HEAD(head, field) do {					\
	if (LIST_FIRST((head)) != NULL &&							\
	    LIST_FIRST((head))->field.le_prev != &LIST_FIRST((head)))	\
		panic("Bad list head %p first->prev != head", (head));	\
} while (0)

/* 调试时检查节点的下一个节点的前驱是否正确 */
#define	QMD_LIST_CHECK_NEXT(elm, field) do {					\
	if (LIST_NEXT((elm), field) != NULL &&						\
	    LIST_NEXT((elm), field)->field.le_prev != &((elm)->field.le_next))	\
	     	panic("Bad link elm %p next->prev != elm", (elm));	\
} while (0)

/* 调试时检查节点的前驱指针是否指向自身 */
#define	QMD_LIST_CHECK_PREV(elm, field) do {					\
	if (*(elm)->field.le_prev != (elm))							\
		panic("Bad link elm %p prev->next != elm", (elm));		\
} while (0)
#else
/* 非调试模式下，检查宏为空 */
#define	QMD_LIST_CHECK_HEAD(head, field)
#define	QMD_LIST_CHECK_NEXT(elm, field)
#define	QMD_LIST_CHECK_PREV(elm, field)
#endif /* (_KERNEL && INVARIANTS) */

/* 双向链表核心操作宏 */

/* 判断双向链表是否为空 */
#define	LIST_EMPTY(head)	((head)->lh_first == NULL)

/* 获取双向链表的第一个节点 */
#define	LIST_FIRST(head)	((head)->lh_first)

/*
 * 正向遍历双向链表（遍历过程中不可删除节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：链表头
 *   field：节点中LIST_ENTRY字段的名称
 */
#define	LIST_FOREACH(var, head, field)							\
	for ((var) = LIST_FIRST((head));							\
	    (var);													\
	    (var) = LIST_NEXT((var), field))

/*
 * 安全正向遍历双向链表（遍历过程中可删除当前节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：链表头
 *   field：节点中LIST_ENTRY字段的名称
 *   tvar：临时变量（保存下一个节点）
 */
#define	LIST_FOREACH_SAFE(var, head, field, tvar)				\
	for ((var) = LIST_FIRST((head));							\
	    (var) && ((tvar) = LIST_NEXT((var), field), 1);		\
	    (var) = (tvar))

/* 动态初始化双向链表（清空链表） */
#define	LIST_INIT(head) do {									\
	LIST_FIRST((head)) = NULL;									\
} while (0)

/*
 * 在指定节点后插入新节点（O(1)）
 * 参数：
 *   listelm：基准节点（新节点插入到它后面）
 *   elm：待插入的新节点
 *   field：节点中LIST_ENTRY字段的名称
 */
#define	LIST_INSERT_AFTER(listelm, elm, field) do {				\
	QMD_LIST_CHECK_NEXT(listelm, field);	/* 调试检查 */			\
	/* 新节点的next指向基准节点的next */							\
	if ((LIST_NEXT((elm), field) = LIST_NEXT((listelm), field)) != NULL)\
		LIST_NEXT((listelm), field)->field.le_prev = &LIST_NEXT((elm), field);	\
	/* 基准节点的next指向新节点，新节点的prev指向基准节点的next地址 */	\
	LIST_NEXT((listelm), field) = (elm);						\
	(elm)->field.le_prev = &LIST_NEXT((listelm), field);		\
} while (0)

/*
 * 在指定节点前插入新节点（O(1)，双向链表特有优势）
 * 参数：
 *   listelm：基准节点（新节点插入到它前面）
 *   elm：待插入的新节点
 *   field：节点中LIST_ENTRY字段的名称
 */
#define	LIST_INSERT_BEFORE(listelm, elm, field) do {			\
	QMD_LIST_CHECK_PREV(listelm, field);	/* 调试检查 */			\
	/* 新节点的prev指向基准节点的prev，新节点的next指向基准节点 */	\
	(elm)->field.le_prev = (listelm)->field.le_prev;			\
	LIST_NEXT((elm), field) = (listelm);						\
	/* 基准节点的prev指向的地址（上一个节点的next）赋值为新节点 */	\
	*(listelm)->field.le_prev = (elm);							\
	/* 基准节点的prev指向新节点的next地址 */						\
	(listelm)->field.le_prev = &LIST_NEXT((elm), field);		\
} while (0)

/*
 * 在链表头部插入新节点（头插法，O(1)）
 * 参数：
 *   head：链表头
 *   elm：待插入的新节点
 *   field：节点中LIST_ENTRY字段的名称
 */
#define	LIST_INSERT_HEAD(head, elm, field) do {					\
	QMD_LIST_CHECK_HEAD((head), field);	/* 调试检查 */			\
	/* 新节点的next指向原头节点 */									\
	if ((LIST_NEXT((elm), field) = LIST_FIRST((head))) != NULL)	\
		LIST_FIRST((head))->field.le_prev = &LIST_NEXT((elm), field);	\
	/* 头指针指向新节点，新节点的prev指向头的first字段地址 */		\
	LIST_FIRST((head)) = (elm);									\
	(elm)->field.le_prev = &LIST_FIRST((head));					\
} while (0)

/* 获取节点的下一个节点 */
#define	LIST_NEXT(elm, field)	((elm)->field.le_next)

/*
 * 从链表中删除指定节点（O(1)，双向链表核心优势）
 * 参数：
 *   elm：待删除的节点
 *   field：节点中LIST_ENTRY字段的名称
 */
#define	LIST_REMOVE(elm, field) do {					\
	QMD_LIST_CHECK_NEXT(elm, field);	/* 调试检查 */	\
	QMD_LIST_CHECK_PREV(elm, field);	/* 调试检查 */	\
	/* 若有下一个节点，更新其prev为当前节点的prev */		\
	if (LIST_NEXT((elm), field) != NULL)				\
		LIST_NEXT((elm), field)->field.le_prev = 		\
		    (elm)->field.le_prev;						\
	/* 当前节点的prev指向的地址（上一个节点的next）更新为当前节点的next */	\
	*(elm)->field.le_prev = LIST_NEXT((elm), field);	\
	TRASHIT((elm)->field.le_next);	/* 标记已删除 */		\
	TRASHIT((elm)->field.le_prev);	/* 标记已删除 */		\
} while (0)

/*
 * 交换两个双向链表的内容（O(1)）
 * 参数：
 *   head1、head2：两个链表头
 *   type：节点的数据类型
 *   field：节点中LIST_ENTRY字段的名称
 */
#define LIST_SWAP(head1, head2, type, field) do {		\
	struct type *swap_tmp = LIST_FIRST((head1));		\
	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
	LIST_FIRST((head2)) = swap_tmp;						\
	/* 若交换后链表非空，更新第一个节点的prev指针 */		\
	if ((swap_tmp = LIST_FIRST((head1))) != NULL)		\
		swap_tmp->field.le_prev = &LIST_FIRST((head1));	\
	if ((swap_tmp = LIST_FIRST((head2))) != NULL)		\
		swap_tmp->field.le_prev = &LIST_FIRST((head2));	\
} while (0)


// ==========================================
// 第四部分：双向尾队列（TAILQ）
// 特性：双向链接+尾指针，融合双向链表的灵活性和尾队列的高效尾操作。
// 优势：支持任意位置插入/删除（O(1)）、双向遍历、高效尾插（O(1)）。
// 劣势：结构最复杂，内存开销略大。
// 适用场景：需要频繁在头尾操作、双向遍历、中间修改的场景（如协程就绪队列）。
// ==========================================

/*
 * 定义双向尾队列的头结构
 * 参数：
 *   name：队列名称
 *   type：节点的数据类型
 * 结构说明：
 *   tqh_first：指向队列的第一个节点
 *   tqh_last：指向队列最后一个节点的"next指针的地址"（用于高效尾插）
 *   TRACEBUF：调试轨迹字段（默认关闭）
 */
#define	TAILQ_HEAD(name, type)										\
	struct name {													\
		struct type *tqh_first; /* 指向第一个节点 */ 				\
		struct type **tqh_last; /* 指向最后一个节点的next指针地址 */ 	\
		TRACEBUF													\
	}

/*
 * 静态初始化双向尾队列头
 * 示例：TAILQ_HEAD(myqueue, node) queue = TAILQ_HEAD_INITIALIZER(queue);
 */
#define	TAILQ_HEAD_INITIALIZER(head)								\
		{ NULL, &(head).tqh_first }

/*
 * 定义双向尾队列的节点结构（每个节点需包含此字段作为链接）
 * 参数：type：节点的数据类型
 * 结构说明：
 *   tqe_next：指向当前节点的下一个节点（后向指针）
 *   tqe_prev：指向当前节点的前一个节点的"tqe_next指针的地址"（前向指针地址）
 *   TRACEBUF：调试轨迹字段（默认关闭）
 */
#define	TAILQ_ENTRY(type)											\
	struct {														\
		struct type *tqe_next;	/* 指向 next 节点 */				\
		struct type **tqe_prev; /* 指向 prev 节点的tqe_next指针地址 */	\
		TRACEBUF													\
	}

/* 双向尾队列核心操作宏（含调试检查，默认关闭） */
#if (defined(_KERNEL) && defined(INVARIANTS))
/* 调试时检查头节点的第一个节点的前驱是否正确 */
#define	QMD_TAILQ_CHECK_HEAD(head, field) do {					\
	if (!TAILQ_EMPTY(head) &&									\
	    TAILQ_FIRST((head))->field.tqe_prev != &TAILQ_FIRST((head)))	\
		panic("Bad tailq head %p first->prev != head", (head));	\
} while (0)

/* 调试时检查尾节点的next是否为NULL */
#define	QMD_TAILQ_CHECK_TAIL(head, field) do {					\
	if (*(head)->tqh_last != NULL)								\
	    	panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); 	\
} while (0)

/* 调试时检查节点的下一个节点的前驱是否正确 */
#define	QMD_TAILQ_CHECK_NEXT(elm, field) do {				\
	if (TAILQ_NEXT((elm), field) != NULL &&					\
	    TAILQ_NEXT((elm), field)->field.tqe_prev != &((elm)->field.tqe_next))	\
		panic("Bad link elm %p next->prev != elm", (elm));	\
} while (0)

/* 调试时检查节点的前驱指针是否指向自身 */
#define	QMD_TAILQ_CHECK_PREV(elm, field) do {				\
	if (*(elm)->field.tqe_prev != (elm))					\
		panic("Bad link elm %p prev->next != elm", (elm));	\
} while (0)
#else
/* 非调试模式下，检查宏为空 */
#define	QMD_TAILQ_CHECK_HEAD(head, field)
#define	QMD_TAILQ_CHECK_TAIL(head, headname)
#define	QMD_TAILQ_CHECK_NEXT(elm, field)
#define	QMD_TAILQ_CHECK_PREV(elm, field)
#endif /* (_KERNEL && INVARIANTS) */

/* 双向尾队列核心操作宏 */

/*
 * 合并两个双向尾队列（将head2合并到head1尾部，head2清空）
 * 参数：
 *   head1：目标队列（合并后保存所有节点）
 *   head2：源队列（合并后为空）
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_CONCAT(head1, head2, field) do {				\
	if (!TAILQ_EMPTY(head2)) {								\
		*(head1)->tqh_last = (head2)->tqh_first;		/* 链接两个队列 */	\
		(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last;	/* 更新head2第一个节点的prev */	\
		(head1)->tqh_last = (head2)->tqh_last;		/* 更新head1的尾指针 */	\
		TAILQ_INIT((head2));					/* 清空head2 */		\
		QMD_TRACE_HEAD(head1);					/* 调试轨迹 */		\
		QMD_TRACE_HEAD(head2);					/* 调试轨迹 */		\
	}													\
} while (0)

/* 判断双向尾队列是否为空 */
#define	TAILQ_EMPTY(head)	((head)->tqh_first == NULL)

/* 获取双向尾队列的第一个节点 */
#define	TAILQ_FIRST(head)	((head)->tqh_first)

/*
 * 正向遍历双向尾队列（遍历过程中不可删除节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_FOREACH(var, head, field)					\
	for ((var) = TAILQ_FIRST((head));					\
	    (var);											\
	    (var) = TAILQ_NEXT((var), field))

/*
 * 安全正向遍历双向尾队列（遍历过程中可删除当前节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   field：节点中TAILQ_ENTRY字段的名称
 *   tvar：临时变量（保存下一个节点）
 */
#define	TAILQ_FOREACH_SAFE(var, head, field, tvar)			\
	for ((var) = TAILQ_FIRST((head));						\
	    (var) && ((tvar) = TAILQ_NEXT((var), field), 1);	\
	    (var) = (tvar))

/*
 * 反向遍历双向尾队列（从最后一个节点到第一个，遍历过程中不可删除节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   headname：队列头的类型名称（用于计算最后一个节点）
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_FOREACH_REVERSE(var, head, headname, field)	\
	for ((var) = TAILQ_LAST((head), headname);				\
	    (var);												\
	    (var) = TAILQ_PREV((var), headname, field))

/*
 * 安全反向遍历双向尾队列（遍历过程中可删除当前节点）
 * 参数：
 *   var：循环变量（当前节点指针）
 *   head：队列头
 *   headname：队列头的类型名称
 *   field：节点中TAILQ_ENTRY字段的名称
 *   tvar：临时变量（保存上一个节点）
 */
#define	TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar)	\
	for ((var) = TAILQ_LAST((head), headname);			\
	    (var) && ((tvar) = TAILQ_PREV((var), headname, field), 1);	\
	    (var) = (tvar))

/* 动态初始化双向尾队列（清空队列） */
#define	TAILQ_INIT(head) do {						\
	TAILQ_FIRST((head)) = NULL;						\
	(head)->tqh_last = &TAILQ_FIRST((head));		/* 尾指针指向头的first字段 */	\
	QMD_TRACE_HEAD(head);							/* 调试轨迹 */		\
} while (0)

/*
 * 在指定节点后插入新节点（O(1)）
 * 参数：
 *   head：队列头（可能需要更新尾指针）
 *   listelm：基准节点（新节点插入到它后面）
 *   elm：待插入的新节点
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_INSERT_AFTER(head, listelm, elm, field) do {		\
	QMD_TAILQ_CHECK_NEXT(listelm, field);	/* 调试检查 */			\
	/* 新节点的next指向基准节点的next */							\
	if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
		TAILQ_NEXT((elm), field)->field.tqe_prev = &TAILQ_NEXT((elm), field);	\
	else {	/* 若插入到尾部，更新队列尾指针 */							\
		(head)->tqh_last = &TAILQ_NEXT((elm), field);	\
		QMD_TRACE_HEAD(head);							\
	}													\
	/* 基准节点的next指向新节点，新节点的prev指向基准节点的next地址 */	\
	TAILQ_NEXT((listelm), field) = (elm);				\
	(elm)->field.tqe_prev = &TAILQ_NEXT((listelm), field);		\
	QMD_TRACE_ELEM(&(elm)->field);						/* 调试轨迹 */	\
	QMD_TRACE_ELEM(&listelm->field);					/* 调试轨迹 */	\
} while (0)

/*
 * 在指定节点前插入新节点（O(1)）
 * 参数：
 *   listelm：基准节点（新节点插入到它前面）
 *   elm：待插入的新节点
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_INSERT_BEFORE(listelm, elm, field) do {		\
	QMD_TAILQ_CHECK_PREV(listelm, field);	/* 调试检查 */			\
	/* 新节点的prev指向基准节点的prev，新节点的next指向基准节点 */	\
	(elm)->field.tqe_prev = (listelm)->field.tqe_prev;		\
	TAILQ_NEXT((elm), field) = (listelm);					\
	/* 基准节点的prev指向的地址（上一个节点的next）赋值为新节点 */	\
	*(listelm)->field.tqe_prev = (elm);						\
	/* 基准节点的prev指向新节点的next地址 */						\
	(listelm)->field.tqe_prev = &TAILQ_NEXT((elm), field);	\
	QMD_TRACE_ELEM(&(elm)->field);							/* 调试轨迹 */	\
	QMD_TRACE_ELEM(&listelm->field);						/* 调试轨迹 */	\
} while (0)

/*
 * 在队列头部插入新节点（头插法，O(1)）
 * 参数：
 *   head：队列头
 *   elm：待插入的新节点
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_INSERT_HEAD(head, elm, field) do {			\
	QMD_TAILQ_CHECK_HEAD(head, field);	/* 调试检查 */			\
	/* 新节点的next指向原头节点 */									\
	if ((TAILQ_NEXT((elm), field) = TAILQ_FIRST((head))) != NULL)	\
		TAILQ_FIRST((head))->field.tqe_prev = &TAILQ_NEXT((elm), field);	\
	else {	/* 若队列为空，尾指针指向新节点的next地址 */				\
		(head)->tqh_last = &TAILQ_NEXT((elm), field);	\
	}																\
	/* 头指针指向新节点，新节点的prev指向头的first字段地址 */		\
	TAILQ_FIRST((head)) = (elm);							\
	(elm)->field.tqe_prev = &TAILQ_FIRST((head));			\
	QMD_TRACE_HEAD(head);									/* 调试轨迹 */	\
	QMD_TRACE_ELEM(&(elm)->field);							/* 调试轨迹 */	\
} while (0)

/*
 * 在队列尾部插入新节点（尾插法，O(1)）
 * 参数：
 *   head：队列头
 *   elm：待插入的新节点
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_INSERT_TAIL(head, elm, field) do {			\
	QMD_TAILQ_CHECK_TAIL(head, field);	/* 调试检查 */			\
	TAILQ_NEXT((elm), field) = NULL;						/* 新节点为最后一个，next为NULL */	\
	(elm)->field.tqe_prev = (head)->tqh_last;				/* 新节点的prev指向队列当前尾指针 */	\
	*(head)->tqh_last = (elm);								/* 尾指针指向的地址赋值为新节点 */	\
	(head)->tqh_last = &TAILQ_NEXT((elm), field);			/* 更新尾指针为新节点的next地址 */	\
	QMD_TRACE_HEAD(head);									/* 调试轨迹 */	\
	QMD_TRACE_ELEM(&(elm)->field);							/* 调试轨迹 */	\
} while (0)

/*
 * 获取双向尾队列的最后一个节点（O(1)）
 * 参数：
 *   head：队列头
 *   headname：队列头的类型名称
 */
#define	TAILQ_LAST(head, headname)							\
	(*(((struct headname *)((head)->tqh_last))->tqh_last))

/* 获取节点的下一个节点 */
#define	TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

/*
 * 获取节点的上一个节点（反向遍历用，O(1)）
 * 参数：
 *   elm：当前节点
 *   headname：队列头的类型名称
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_PREV(elm, headname, field)					\
	(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))

/*
 * 从队列中删除指定节点（O(1)）
 * 参数：
 *   head：队列头（可能需要更新尾指针）
 *   elm：待删除的节点
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define	TAILQ_REMOVE(head, elm, field) do {				\
	QMD_TAILQ_CHECK_NEXT(elm, field);	/* 调试检查 */	\
	QMD_TAILQ_CHECK_PREV(elm, field);	/* 调试检查 */	\
	/* 若有下一个节点，更新其prev为当前节点的prev */		\
	if ((TAILQ_NEXT((elm), field)) != NULL)			\
		TAILQ_NEXT((elm), field)->field.tqe_prev = 		\
		    (elm)->field.tqe_prev;						\
	else {	/* 若删除的是尾节点，更新队列尾指针 */			\
		(head)->tqh_last = (elm)->field.tqe_prev;		\
		QMD_TRACE_HEAD(head);							\
	}													\
	/* 当前节点的prev指向的地址（上一个节点的next）更新为当前节点的next */	\
	*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);	\
	TRASHIT((elm)->field.tqe_next);	/* 标记已删除 */		\
	TRASHIT((elm)->field.tqe_prev);	/* 标记已删除 */		\
	QMD_TRACE_ELEM(&(elm)->field);		/* 调试轨迹 */		\
} while (0)

/*
 * 交换两个双向尾队列的内容（O(1)）
 * 参数：
 *   head1、head2：两个队列头
 *   type：节点的数据类型
 *   field：节点中TAILQ_ENTRY字段的名称
 */
#define TAILQ_SWAP(head1, head2, type, field) do {		\
	struct type *swap_first = (head1)->tqh_first;		\
	struct type **swap_last = (head1)->tqh_last;		\
	(head1)->tqh_first = (head2)->tqh_first;			\
	(head1)->tqh_last = (head2)->tqh_last;				\
	(head2)->tqh_first = swap_first;					\
	(head2)->tqh_last = swap_last;						\
	/* 若交换后队列非空，更新第一个节点的prev指针 */		\
	if ((swap_first = (head1)->tqh_first) != NULL)		\
		swap_first->field.tqe_prev = &(head1)->tqh_first;	\
	else								\
		(head1)->tqh_last = &(head1)->tqh_first;		\
	if ((swap_first = (head2)->tqh_first) != NULL)		\
		swap_first->field.tqe_prev = &(head2)->tqh_first;	\
	else								\
		(head2)->tqh_last = &(head2)->tqh_first;		\
} while (0)

#endif	/* __NTY_QUEUE_H__ */